The success of the Internet can be largely attributed to the proliferation of online services. Online services play an indispensable role in people's daily lives, providing open and free access to activities such as email, search, social networking, and blogging. The popularity of the services and the open access model have, in turn, attracted attackers to leverage these free resources as a major attack venues. Within the last few years, millions of malicious accounts and their nefarious activities—including spam, phishing, social scam, and malware propagation—have become a pervasive problem throughout the Internet.
CAPTCHAs are widely deployed to prevent attackers from abusing services at a large scale. A CAPTCHA test typically has a user type letters or digits from a distorted image, which is easier to read for humans than for automated programs. CAPTCHAs are usually given to a user at service sign-up time and also frequently afterwards until the user establishes reputation. Although they are often effective to distinguish human users from bots, attackers have various mechanisms to bypass CAPTCHAs, such as by hiring cheap human labor.
It is commonly recognized that the social network structure may contribute to the defense against attacker created accounts, since a legitimate user would rarely establish connections with attackers. However, attackers are increasingly compromising legitimate user accounts, and using those accounts to connect to other malicious accounts. These malicious users invalidate the assumption that a legitimate user would rarely establish connections with other malicious users, and make preventing malicious attacks by leveraging social network relationships difficult.